package aishua.com.mytestapplist.datastructure;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by aishua on 2018/4/19.
 * 线性表的顺序存储结构
 */

public class SeqList<T> implements LList<T>{
//   数据元素
    protected Object[] element;
//    线性列表数据元素个数
    protected int length;

    public SeqList(){

        this(64);
    }
    public SeqList(int size){

        element =new Object[size];
        this.length = 0;

    }
    @Override
    public boolean isEmpty() {

        return this.length ==0;
    }

    @Override
    public int length() {

        return this.length;
    }

    @Override
    public T getElem(int i) {

        if (i>0 && i <this.length){
            return (T) element[i];
        }
        return null;
    }

    /*
     设置第i个元素的值为t
    *
    * */
    @Override
    public void set(int i, T t) {
         if (t ==null){

             throw new NullPointerException("插入的值为空t==null");
         }
        if (i >0 && i <length){

            element[i] = t;
        }else {

            throw new IndexOutOfBoundsException("设置元素的值下标越界i=="+i);
        }

    }
/*
*i应该是从0开始计数，意思是可以为0
* 线性表顺序存储结构在第i个位置插入元素x,如果i<0,则插入到首位，如果i>数据长度，则插入到末尾
* */
    @Override
    public void insert(int i, T x) {

        if ( x ==null){
            return;
        }
//        数据元素长度达到最大，进行扩容
        if (length ==element.length){
            Object[] temp = element;
            element = new Object[temp.length *2];
            for (int j=0;j<temp.length;j++){
                element[j] =temp[j];
            }
        }
//        进行容错
        if (i < 0){
            i =0;
        }
        if (i >length){

            i =length;
        }
        for (int j=length-1;j >i-1;j--){

            element[j+1] =element[j];
        }
        element[i] =x;
        length ++;

    }
/*
* 末尾插入数据
* */
    @Override
    public void append(T x) {

        insert(length,x);
    }

    @Override
    public T remove(int i) {

//        容错处理
        if (i <0){
            i =0;
        }
        if (i >  length){
            i= length;
        }
         T temp = (T) element[i];
        for (int j =i;j < element.length -1;j++){
            element[i] = element[i+1];
        }
        element[length-1] =null;
        length--;
        return temp;
    }

    @Override
    public void removeAll() {

        this.length =0;
    }

    @Override
    public T search(T key) {

        int find =indexOf(key);
        return find==-1 ? null : (T) element[find];
    }

//线性表的顺序存储结构，数据元素必须重写equals方法，要不然没法比较
    @Override
    public boolean equals(Object object) {

        if (this == object){

            return true;
        }
        if (object instanceof SeqList){

            SeqList<T> list = (SeqList<T>) object;

            for (int i =0;i < length ;i++){

                if (!list.getElem(i).equals(element[i])){

                    return false;
                }
                return true;
            }
        }
        return false;
    }

     public int indexOf(T t){

         if (t !=null) {

             for (int i=0;i <length;i++){

                 if (t.equals(element[i])){
                     return i;
                 }

             }
         }
         return -1;
     }
}
